package
{
	import de.polygonal.math.PM_PRNG;
	
	import flash.display.Sprite;
	import flash.display.StageAlign;
	import flash.display.StageScaleMode;
	import flash.events.MouseEvent;
	import flash.events.TimerEvent;
	import flash.geom.Point;
	import flash.geom.Rectangle;
	import flash.utils.Timer;
	import flash.utils.getTimer;
	
	public class skipquad extends Sprite
	{

		
		public static var quadTreeSprite:Sprite;
		public static var quadTreeSprite2:Sprite;
		
		public static var overlayLayer:Sprite;
		public static var overlayLayer2:Sprite = new Sprite();
		
		public static const NUM_POINTS:int = 70;
		public var tick:Timer = new Timer(250);

		public var points:Vector.<Point>;
		public var startTime:int;
		public var paused:Boolean = false;
		
		public function skipquad()
		{
			
			var skipList:SkipList = new SkipList();
			startTime = getTimer();
			var jl:int, j:int;
			
			stage.scaleMode = StageScaleMode.NO_SCALE;
			stage.align = StageAlign.TOP_LEFT;
			
			Global.prng = new PM_PRNG();
			Global.prng.seed = 1234;
			
			points = generateRandomPoints();

			stage.addEventListener(MouseEvent.CLICK, function():void{
				paused = !paused;
			});
			
			testSkipList();
			//testMazeGeneration();
			//testBinaryHeap();
			//testQuadTree();
			//visiualizeOverTime();
			//quadtree();
		}
		
		
		public static function clamp(pnt:Point, amount:Number):Point{
			return new Point(Math.floor(pnt.x/amount)*amount, Math.floor(pnt.y/amount)*amount);
		}
		
		public function testMazeGeneration():void{
			var maze:Maze = new Maze(new Rectangle(0,0,Maze.CELL_SIZE*25,Maze.CELL_SIZE*25));
			maze.generate();
			var mazeImage:Sprite = maze.draw();
			addChild(mazeImage);
			
			var destination:Point;
			mazeImage.addEventListener(MouseEvent.CLICK, function(me:MouseEvent):void{
				if(!destination){
					destination = clamp(new Point(me.stageX, me.stageY), Maze.CELL_SIZE);
				}
				else{
					var nextObj:Pather = new Pather(clamp(new Point(me.stageX, me.stageY), Maze.CELL_SIZE));
					nextObj.destination = destination.clone();
					
				}
			});
			var timer:Timer = new Timer(1000);
			timer.addEventListener(TimerEvent.TIMER, function(te:TimerEvent):void{
				if(paused){
					return;
				}
				
				
			});
			
			timer.start();
		}
		
		public function pnt2idx(pnt:Point):String{
			return String(pnt.x) + "," + String(pnt.y);
		}
		
		public function testBinaryHeap():void{
			var binaryHeap:BinaryHeap = new BinaryHeap();
			var i:int, il:int;
			for(i = 0, il = points.length; i < il; i++){
				binaryHeap.insert(Math.floor(points[i].x),points[i]);	
			}
			
			for(i = 0, il = points.length/2; i < il; i++){
				binaryHeap.remove();	
			}	
			
			for(i = 0, il = points.length; i < il; i++){
				binaryHeap.insert(Math.floor(points[i].x),points[i]);	
			}			
			
			var drawing:Sprite = binaryHeap.getDrawing();
			addChild(drawing);
			drawing.x = drawing.width/2;
			
			
//			var removedNumbers:Array = new Array();
////			for(i = 0, il = points.length; i < il; i++){
//			for(i = 0, il = 1; i < il; i++){	
//				binaryHeap.remove();	
//			}
			
			var values:Array = new Array();
			i = 0;
			tick.addEventListener(TimerEvent.TIMER, function(te:TimerEvent):void{
				if(paused){
					return;
				}

				values.push(binaryHeap.remove().data.value);
				drawing.parent.removeChild(drawing);
				drawing = binaryHeap.getDrawing();
				addChild(drawing);
				drawing.x = drawing.width/2;
				i++;
			});
			tick.start();			
			
		}
		
		public function quadtree():void{
			var i:int, il:int;
			var skipQuad:SkipQuadtree = new SkipQuadtree();
			for(i = 0, il = points.length; i < il; i++){
				skipQuad.insert(points[i]);	
			}
			
			quadTreeSprite = skipQuad.createImage();
			addChild(quadTreeSprite);
			quadTreeSprite.x = quadTreeSprite.width/2;
			quadTreeSprite.y = quadTreeSprite.height/2;	
			
		}
		
		public function testSkipList():void{
			
			
			var i:int, il:int;
			var values:Array = new Array();
			var skipList:SkipList = new SkipList();
			for(i = 0, il = points.length; i < il; i++){
				skipList.insert(points[i].x);
			}
			
			trace(getTimer() - startTime);			
			var values2:Array = skipList.getSortedList();					
			trace(getTimer() - startTime);
			
			
			//				skipList.insert(points[i].x);
			//				var values2:Array = skipList.getSortedList();	
			//				for(j = 0, jl = values2.length; j < jl; j++){
			//					if(values2[j] && values2[j+1]){
			//						if(values2[j] > values2[j+1]){
			//							trace("sort error");
			//							throw new Error("exit");
			//						}
			//					}
			//				}			
		}
		
		public function testQuadTree():void{
			var i:int, il:int;
			var j:int = 0;
			var skipQuad:SkipQuadtree = new SkipQuadtree();
			var compressedQuad:SkipQuadtree = new SkipQuadtree(true);
			var list:Vector.<Point> = new Vector.<Point>;
			
			startTime = getTimer();
			for(i = 0, il = points.length; i < il; i++){
				skipQuad.insert(points[i]);	
			}
			trace("Quad Insert: " + (getTimer() - startTime));
			
			startTime = getTimer();
			for(i = 0, il = points.length; i < il; i++){
				compressedQuad.insert(points[i]);	
			}
			trace("Compressed Quad Insert: " + (getTimer() - startTime));					
			
			startTime = getTimer();
			for(i = 0, il = points.length; i < il; i++){
				list.push(points[i]);	
			}
			trace("List Insert: " + (getTimer() - startTime));	
		
			startTime = getTimer();
			for(i = 0, il = points.length; i < il; i++){
				if(!skipQuad.find(points[i])){
					trace("WTF" + (j++) + " : " + points[i].x + "," + points[i].y);
				}
			}
			
			trace("Quad Search: " + (getTimer() - startTime) + " depth: " + skipQuad.getDepth());
			
			startTime = getTimer();
			j = 0;
			for(i = 0, il = points.length; i < il; i++){
				if(!compressedQuad.find(points[i])){
					trace("wtf" + (j++));
				}
			}
			trace("CompressedSearch Search: " + (getTimer() - startTime) + " depth: " + skipQuad.getDepth());			
			
//			startTime = getTimer();
//			for(i = 0, il = points.length; i < il; i++){
//				points.indexOf(points[i])	
//			}
//			trace("List Search: " + (getTimer() - startTime));			
		}
		
		public function visiualizeOverTime():void{
			var i:int;
			var skipQuad:SkipQuadtree = new SkipQuadtree();
			var skipQuad2:SkipQuadtree = new SkipQuadtree(true);
			var direction:Boolean = true;
			i = 0;

			
			quadTreeSprite = new Sprite();
			quadTreeSprite2 = new Sprite();
			addChild(quadTreeSprite);
			addChild(quadTreeSprite2);
			addChild(overlayLayer2);
			tick.addEventListener(TimerEvent.TIMER, function(te:TimerEvent):void{
				if(paused){
					return;
				}
				Global.prng = new PM_PRNG;
				Global.prng.seed = 1231231232;
				if(points.length > i && direction){
					skipQuad.insert(points[i]);	
					skipQuad2.insert(points[i]);
					
					quadTreeSprite.parent.removeChild(quadTreeSprite);
					quadTreeSprite = skipQuad.createImage();
					addChild(quadTreeSprite);
					quadTreeSprite.x = quadTreeSprite.width/2;
					quadTreeSprite.y = quadTreeSprite.height/2;
					overlayLayer = new Sprite();
					overlayLayer.graphics.drawRect(quadTreeSprite.x, quadTreeSprite.y, quadTreeSprite.width, quadTreeSprite.height);
					
					quadTreeSprite2.parent.removeChild(quadTreeSprite2);
					quadTreeSprite2 = skipQuad2.createImage();
					addChild(quadTreeSprite2);
					quadTreeSprite2.x = quadTreeSprite.x + quadTreeSprite.width + 50;
					quadTreeSprite2.y = quadTreeSprite2.height/2;
					
					skipQuad.find(points[i]);
					skipQuad2.find(points[i]);
					
					i++;
				}
				else
				if(points.length > i && !direction){
					skipQuad.remove(points[points.length-i-1]);	
					quadTreeSprite.parent.removeChild(quadTreeSprite);
					quadTreeSprite = skipQuad.createImage();
					addChild(quadTreeSprite);
					quadTreeSprite.x = quadTreeSprite.width/2;
					quadTreeSprite.y = quadTreeSprite.height/2;		
					
					skipQuad2.remove(points[points.length-i-1]);	
					quadTreeSprite2.parent.removeChild(quadTreeSprite2);
					quadTreeSprite2 = skipQuad.createImage();
					addChild(quadTreeSprite2);
					quadTreeSprite2.x = quadTreeSprite.x + quadTreeSprite.width + 50;
					quadTreeSprite2.y = quadTreeSprite2.height/2;					
					
					i++;
				}
				else{
					i = 0;
					direction = !direction;
				}
			});
			tick.start();			
		}
		
		private function generateRandomPoints():Vector.<Point>{
			var i:int;
			var points:Vector.<Point> = new Vector.<Point>;
//			for(i = 0; i < 10000*3; i++){
			for(i = 0; i < NUM_POINTS; i++){		
				points.push(new Point(
					SkipQuadtree.QUAD_SIZE.left + Global.prng.nextDouble()*SkipQuadtree.QUAD_SIZE.width,
					SkipQuadtree.QUAD_SIZE.top + Global.prng.nextDouble()*SkipQuadtree.QUAD_SIZE.height
				));				
				
				// shows how a compressed list worst case scenerio not exponentially getting worse
//				points.push(new Point(
//					(SkipQuadtree.QUAD_SIZE.left + Global.prng.nextDouble()*SkipQuadtree.QUAD_SIZE.width)/Math.pow(2,200),
//					(SkipQuadtree.QUAD_SIZE.top + Global.prng.nextDouble()*SkipQuadtree.QUAD_SIZE.height)/ Math.pow(2,200)
//				));	
				
//				points.push(new Point(i*Math.pow(2,1),i*Math.pow(2,1)));				
			}
			
			return points;
		}
	}
}